package org.example.myleet.p1220;

public class Solution {
//    public int countVowelPermutation(int n) {
//        int MOD = 1000000007;
//        //0-a, 1-e, 2-i, 3-o, 4-u
//        long[][] dp = new long[n + 1][5];
//        for (int j = 0; j < 5; ++j) {
//            dp[1][j] = 1;
//        }
//        int lastI;
//        for (int i = 2; i <= n; ++i) {
//            lastI = i - 1;
//            dp[i][0] = (dp[lastI][1] + dp[lastI][2] + dp[lastI][4]) % MOD;
//            dp[i][1] = (dp[lastI][0] + dp[lastI][2]) % MOD;
//            dp[i][2] = (dp[lastI][1] + dp[lastI][3]) % MOD;
//            dp[i][3] = (dp[lastI][2]) % MOD;
//            dp[i][4] = (dp[lastI][2] + dp[lastI][3]) % MOD;
//        }
//        return (int) ((dp[n][0] + dp[n][1] + dp[n][2] + dp[n][3] + dp[n][4]) % MOD);
//    }

    public int countVowelPermutation(int n) {
        int MOD = 1000000007;
        //0-a, 1-e, 2-i, 3-o, 4-u
        long[][] dp = new long[2][5];
        for (int j = 0; j < 5; ++j) {
            dp[0][j] = 1;
        }
        int lastI = 0, thisI = 1;
        for (int i = 1; i < n; ++i) {
            dp[thisI][0] = (dp[lastI][1] + dp[lastI][2] + dp[lastI][4]) % MOD;
            dp[thisI][1] = (dp[lastI][0] + dp[lastI][2]) % MOD;
            dp[thisI][2] = (dp[lastI][1] + dp[lastI][3]) % MOD;
            dp[thisI][3] = (dp[lastI][2]) % MOD;
            dp[thisI][4] = (dp[lastI][2] + dp[lastI][3]) % MOD;
            int t = lastI;
            lastI = thisI;
            thisI = t;
        }
        return (int) ((dp[lastI][0] + dp[lastI][1] + dp[lastI][2] + dp[lastI][3] + dp[lastI][4]) % MOD);
    }
}
